package main

import "go-leetcode/leetcode/utils"

// 148. 排序链表
func main() {
	head := utils.GetListNodeByArray([]int{-1, 5, 3, 4, 0})

	head = sortList(head)

	for head != nil {
		print(head.Val)
		head = head.Next
	}

}

func sortList(head *utils.ListNode) *utils.ListNode {
	if head == nil {
		return nil
	}
	if head.Next == nil {
		return head
	}

	slow, fast := head, head.Next

	for fast.Next != nil {
		slow = slow.Next
		fast = fast.Next
		if fast.Next != nil {
			fast = fast.Next
		}
	}

	mid := slow
	midNext := mid.Next
	mid.Next = nil

	leftNodes := sortList(head)
	rightNodes := sortList(midNext)
	return selfMergeTwoLists(leftNodes, rightNodes)
}

//func sortList(head *utils.ListNode) *utils.ListNode {
//	// 使用归并排序
//	return sort2(head, nil)
//}

func sort2(head *utils.ListNode, tail *utils.ListNode) *utils.ListNode {
	if head == nil {
		return nil
	}

	if head.Next == tail {
		head.Next = nil
		return head
	}

	slow, fast := head, head

	for fast != tail {
		slow = slow.Next
		fast = fast.Next
		if fast != tail {
			fast = fast.Next
		}
	}

	mid := slow
	leftNodes := sort2(head, mid)
	rightNodes := sort2(mid, tail)
	return selfMergeTwoLists(leftNodes, rightNodes)
}

func selfMergeTwoLists(list1 *utils.ListNode, list2 *utils.ListNode) *utils.ListNode {
	//if list1 == nil {
	//	return list2
	//}
	//if list2 == nil {
	//	return list1
	//}
	pointHead := &utils.ListNode{}
	pointNode := pointHead
	for list1 != nil || list2 != nil {
		if list1 == nil {
			pointNode.Next = list2
			return pointHead.Next
		}
		if list2 == nil {
			pointNode.Next = list1
			return pointHead.Next
		}

		if list1.Val < list2.Val {
			pointNode.Next = list1
			list1 = list1.Next
		} else {
			pointNode.Next = list2
			list2 = list2.Next
		}
		pointNode = pointNode.Next
	}

	return pointHead.Next
}

// 给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。
//
//示例 1：
//
//输入：head = [4,2,1,3]
//输出：[1,2,3,4]
//示例 2：
//
//输入：head = [-1,5,3,4,0]
//输出：[-1,0,3,4,5]
//示例 3：
//
//输入：head = []
//输出：[]
//
//提示：
//
//链表中节点的数目在范围 [0, 5 * 104] 内
//-105 <= Node.val <= 105
//
//进阶：你可以在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序吗？
